package sort;

public class QuickSort {
    /**
     * 总结：
     * 递归排序的优化有两种：
     * 1：
     *      使用三数取中法使得左右两边元素个数尽量平衡，从而减少递归层次
     * 2：
     *      快排的递归过程如同二叉树，而二叉树往往是最后两层的节点个数最多
     *      故可以在递归层次靠近最后时，使用直接插入排序，可以有效减少递归层次*/
    /**
     * 快速排序：
     * 快速排序的时间复杂度主要看递归的深度
     * 故我们若是想对快速排序进行优化，则可以从降低树的高度入手，也就是调整基准值*/


    /**
     * 三数取中-优化排序*/
    private static void optimizeQuick(int[] array, int start, int end) {
        if(start>=end) {
            return;
        }
        //先调整最优基准值
        int midIndex = middleNumberIndex(array,start,end);
        swap(array,midIndex,start);

        //按照基准值分割
        int pivot = partition(array,start,end);

        //递归
        optimizeQuick(array,start,pivot-1);
        optimizeQuick(array,pivot+1,end);
    }

    /**
     * 三数取中+直接插入排序-优化排序*/
    private static void insertOptimizeQuick(int[] array, int start, int end) {
        if(start>=end) {
            return;
        }
        /*当每个分支的值足够小时，其也必定趋近于有序
        * 而根据二叉树的节点分布来说，最后两层的节点个数占据节点总数的一半
        * 故我们可以设定当元素小于指定个数时，直接使用直接插入排序，减少递归次数（预计至少减少一半递归次数）*/
        if(end - start < 25) {
            insertSort(array,start,end);
            return;
        }

        //先调整最优基准值
        int midIndex = middleNumberIndex(array,start,end);
        swap(array,midIndex,start);

        //按照基准值分割
        int pivot = partition(array,start,end);

        //递归
        optimizeQuick(array,start,pivot-1);
        optimizeQuick(array,pivot+1,end);
    }

    /**
     * 原型未优化排序*/

    private static void quick(int[] array, int start, int end) {
        if(start>=end) {
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    //调整基准值
    private static int middleNumberIndex(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if(array[left]<array[right]) {
            if(array[mid]<array[left]) {
                return left;
            } else if(array[mid]>array[right]){
                return right;
            } else {
                return mid;
            }
        } else {
            if(array[mid]<array[right]) {
                return right;
            } else if(array[mid]>array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    //对指定区间的数进行快速排序
    public static void insertSort(int[] array, int start, int end) {
        for(int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            while(j>=start) {
                if(array[j]>tmp) {
                    array[j+1] = array[j];
                    j--;
                } else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    //按照基准值分割
    private static int partition(int[] array, int left, int right) {
        //默认基准值为left
        int target = array[left];
        int record = left;
        while(left<right) {
            while(left<right && array[right]>=target) {
                right--;
            }
            while(left<right && array[left]<=target) {
                left++;
            }
            swap(array,left,right);
        }
        swap(array,record,left);
        return left;
    }

    //交换
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 测试运行速度*/
    public static void test1(int[] array) {
        int[] tmp = array;

        long start = System.currentTimeMillis();
        quickSortTestThree(tmp);
        long end = System.currentTimeMillis();
        System.out.println("超级优化排序用时："+(end-start));
    }
    public static void test2(int[] array) {
        int[] tmp = array;

        long start = System.currentTimeMillis();
        quickSortTestTwo(tmp);
        long end = System.currentTimeMillis();
        System.out.println("优化排序用时："+(end-start));
//        System.out.println("排序如下：");
//        for(int x:tmp) {
//            System.out.print(x+" ");
//        }
    }
    public static void test3(int[] array) {
        int[] tmp = array;

        long start = System.currentTimeMillis();
        quickSortTestOne(tmp);
        long end = System.currentTimeMillis();
        System.out.println("无优化排序用时："+(end-start));
    }
    public static void test4(int[] array) {
        int[] tmp = array;

        long start = System.currentTimeMillis();
        insertSort(tmp,0,tmp.length-1);
        long end = System.currentTimeMillis();
        System.out.println("直接插入排序用时："+(end-start));
    }
    /**
     * 未优化*/
    public static void quickSortTestOne(int[] array) {
        quick(array,0,array.length-1);
    }

    /**
     * 优化*/
    public static void quickSortTestTwo(int[] array) {
        optimizeQuick(array,0,array.length-1);
    }

    /**
     * 超级优化*/
    public static void quickSortTestThree(int[] array) {
        insertOptimizeQuick(array,0,array.length-1);
    }
}
